package com.yc.algorithm.leetcode;

import com.yc.java8.inter.A;
import org.w3c.dom.ls.LSOutput;

import java.util.*;

/**
 * leetcode 100题
 * <href a="https://leetcode-cn.com/problem-list/2cktkvj/">leetcode100题</href>
 * @author samuelchen
 * @version 1.0
 * @date 2022-01-11
 */
public class Leetcode100Solution {

    /**
     * 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
     * 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
     * P   A   H   N
     * A P L S I I G
     * Y   I   R
     * 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
     * 请你实现这个将字符串进行指定行数变换的函数：
     * string convert(string s, int numRows);
     *
     * 示例 1：
     *
     * 输入：s = "PAYPALISHIRING", numRows = 3
     * 输出："PAHNAPLSIIGYIR"
     * 示例 2：
     * 输入：s = "PAYPALISHIRING", numRows = 4
     * 输出："PINALSIGYAHRPI"
     * 解释：
     * P     I    N
     * A   L S  I G
     * Y A   H R
     * P     I
     */
    public String convert(String s, int numRows) {
        if (numRows < 2) {
            return s;
        }

        List<StringBuffer> rows = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            rows.add(new StringBuffer());
        }

        int i = 0, flag = -1;
        for (char c : s.toCharArray()) {
            rows.get(i).append(c);
            if (i == 0 || i == numRows - 1) {
                flag = -flag;
            }
            i += flag;
        }

        StringBuilder res = new StringBuilder();
        for (StringBuffer row : rows) {
            res.append(row);
        }

        return res.toString();
    }

    /**
     * NO.10
     * <code>正则匹配</code>
     * 给你一个字符串s和一个字符规律p，请你来实现一个支持 '.'和'*'的正则表达式匹配。
     *
     * '.' 匹配任意单个字符
     * '*' 匹配零个或多个前面的那一个元素
     * @author samuelchen
     * @date 2022/1/11
     * @param s
     * @param p
     * @throws
     * @return boolean
     */
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }

    private boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }

    /**
     * NO.11
     * 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
     * 在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。
     * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
     *
     * 说明：你不能倾斜容器.
     * eg:
     * 输入：[1,8,6,2,5,4,8,3,7]
     * 输出：49
     * @author samuelchen
     * @date 2022/1/11
     * @param height 
     * @throws 
     * @return int
     */
    public int maxArea(int[] height) {
        // 双指针解法
        int l = 0, r = height.length - 1;
        int ans = 0;
        while (l < r) {
            int area = Math.min(height[l], height[r]) * (r - l);
            ans = Math.max(ans, area);
            if (height[l] <= height[r]) {
                ++l;
            } else {
                --r;
            }
        }
        return ans;
    }

    /**
     * 给定一个整数数组 nums 和一个整数目标值 target，
     * 请你在该数组中找出 和为目标值 target  的那 两个 整数，
     * 并返回它们的数组下标。
     * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
     *
     * 你可以按任意顺序返回答案。
     *
     * @author samuelchen
     * @date 2022/1/11
     * @param nums
     * @param target
     * @throws
     * @return int[]
     */
    public int[] twoSum(int[] nums, int target) {
        // 通过hash表

        return null;
    }


    /**
     * 给你一个包含 n 个整数的数组 nums，
     * 判断 nums 中是否存在三个元素 a，b，c ，
     * 使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
     *
     * 注意：答案中不可以包含重复的三元组。
     *
     * @author samuelchen
     * @date 2022/1/11
     * @param nums
     * @throws
     * @return java.util.List<java.util.List<java.lang.Integer>>
     */
    public List<List<Integer>> threeSum2(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            // 边界判断
            if (nums[i] > 0) {
                return result;
            }
            if (i > 0 && nums[i] == nums[i-1]) continue;

            int cur = nums[i];
            int l = i + 1;
            int r = len - 1;
            while (l < r) {
                int temp = cur + nums[l] + nums[r];
                if (temp == 0) {
                    result.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    while (l < r && nums[l + 1] == nums[l]) ++l;
                    while (l < r && nums[r - 1] == nums[r]) --r;
                    ++l;
                    --r;
                } else if (temp < 0) {
                    ++l;
                } else {
                    --r;
                }
            }
        }
        return result;
    }



    /**
     * 给你一个包含 n 个整数的数组 nums，
     * 判断 nums 中是否存在三个元素 a，b，c ，
     * 使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
     *
     * 注意：答案中不可以包含重复的三元组。
     * 废弃 没有考虑重复元素
     * @author samuelchen
     * @date 2022/1/11
     * @param nums 
     * @throws 
     * @return java.util.List<java.util.List<java.lang.Integer>>
     */
    public List<List<Integer>> threeSum(int[] nums) {
        // 思路：按正负数分组
        // 正负双指针
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> positiveNums = new ArrayList<>();
        List<Integer> negativeNums = new ArrayList<>();
        List<Integer> zeroNums = new ArrayList<>();
        for (int num : nums) {
            if (num > 0) {
                positiveNums.add(num);
            } else if (num == 0) {
                zeroNums.add(num);
            } else {
                negativeNums.add(num);
            }
        }
        // 边界处理
        if (zeroNums.size() == 3) {
            result.add(zeroNums);
        }
        if (positiveNums.size() == 0 || negativeNums.size() == 0) {
            return result;
        }
        Map<Integer, Integer> positiveMap = toMap(positiveNums);
        Map<Integer, Integer> negativeMap = toMap(negativeNums);

        // 双指针逻辑处理
        int positiveIndex = 0;
        int negativeIndex = 0;
        while(negativeIndex < negativeNums.size()){
            int negativeNum = negativeNums.get(negativeIndex);
            while (positiveIndex < positiveNums.size()) {
                int positiveNum = positiveNums.get(positiveIndex);
                int oddTemp = negativeNum + positiveNum;
                List<Integer> list = new ArrayList<>();
                if (oddTemp > 0 && positiveMap.get(-1 * oddTemp) != null && negativeMap.get(-1 * oddTemp) != negativeNum) {
                    list.add(negativeNum);
                    list.add(negativeMap.get(-1 * oddTemp));
                    list.add(positiveNum);
                    result.add(list);
                    positiveIndex++;
                    break;
                }
                if (oddTemp == 0 && zeroNums.size() > 0) {
                    list.add(negativeNum);
                    list.add(zeroNums.get(0));
                    list.add(positiveNum);
                    result.add(list);
                    positiveIndex++;
                    break;
                }
                if (oddTemp < 0 && positiveMap.get(-1 * oddTemp) != null && positiveMap.get(-1 * oddTemp) != positiveNum) {
                    list.add(negativeNum);
                    list.add(positiveMap.get(-1 * oddTemp));
                    list.add(positiveNum);
                    result.add(list);
                    positiveIndex++;
                    break;
                }
                positiveIndex++;
            }
            negativeIndex++;
        }

        return result;
    }

    private static Map<Integer, Integer> toMap(List<Integer> nums) {
        Map<Integer, Integer> numMap = new HashMap<>();
        for (int i = 0; i < nums.size(); i++) {
            numMap.put(nums.get(i), i);
        }
        return numMap;
    }
}

class Test{
    public static void main(String[] args) {
//        Leetcode100Solution solution = new Leetcode100Solution();
//        int[] nums = new int[]{-1,0,1,2,-1,-4};
//        List<List<Integer>> lists = solution.threeSum2(nums);
//        lists.forEach(e -> {
//            e.forEach(e2 -> System.out.print(e2));
//        });

//        Solution100 s = new Solution100();
//        s.letterCombinations("23").forEach(System.out::println);
    }
}